# searchAgents.py
# ---------------
# Licensing Information:  You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
# 
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).


"""
This file contains all of the agents that can be selected to control Pacman.  To
select an agent, use the '-p' option when running pacman.py.  Arguments can be
passed to your agent using '-a'.  For example, to load a SearchAgent that uses
depth first search (dfs), run the following command:

> python pacman.py -p SearchAgent -a fn=depthFirstSearch

Commands to invoke other search strategies can be found in the project
description.

Please only change the parts of the file you are asked to.  Look for the lines
that say

"*** YOUR CODE HERE ***"

The parts you fill in start about 3/4 of the way down.  Follow the project
description for details.

Good luck and happy searching!

您填写的部分大约从 3/4 开始向下。 关注项目
描述了解详细信息。

祝你好运, 祝你搜索愉快！
"""

from typing import List, Tuple, Any
from game import Directions
from game import Agent
from game import Actions
import util
import time
import search
import pacman

class GoWestAgent(Agent):
    "An agent that goes West until it can't."
    "一个向西走直到它不能的代理人"

    def getAction(self, state):
        "The agent receives a GameState (defined in pacman.py)."
        "代理接收游戏状态(在 pacman.py 中定义)"
        if Directions.WEST in state.getLegalPacmanActions():
            return Directions.WEST
        else:
            return Directions.STOP

#######################################################
# This portion is written for you, but will only work #
#       after you fill in parts of search.py          #
#######################################################
#  这部分是为您编写的, 但只有在您填写了 search.py 的部分内容后才能工作   

class SearchAgent(Agent):
    """
    This very general search agent finds a path using a supplied search
    algorithm for a supplied search problem, then returns actions to follow that
    path.
    这个非常通用的搜索代理使用提供的搜索查找路径提供的搜索问题的算法, 然后返回要遵循的操作路径。

    As a default, this agent runs DFS on a PositionSearchProblem to find
    location (1,1)
    默认情况下, 此代理在位置搜索问题上运行 DFS 以查找位置 (1, 1)

    Options for fn include:
      depthFirstSearch or dfs
      breadthFirstSearch or bfs
    FN 的选项包括：
        深度优先搜索或 dfs
        广度第一搜索或 bfs


    Note: You should NOT change any code in SearchAgent
    注意：您不应更改搜索代理中的任何代码
    """

    def __init__(self, fn='depthFirstSearch', prob='PositionSearchProblem', heuristic='nullHeuristic'):
        # Warning: some advanced Python magic is employed below to find the right functions and problems

        # Get the search function from the name and heuristic
        if fn not in dir(search):
            raise AttributeError(fn + ' is not a search function in search.py.')
        func = getattr(search, fn)
        if 'heuristic' not in func.__code__.co_varnames:
            print('[SearchAgent] using function ' + fn)
            self.searchFunction = func
        else:
            if heuristic in globals().keys():
                heur = globals()[heuristic]
            elif heuristic in dir(search):
                heur = getattr(search, heuristic)
            else:
                raise AttributeError(heuristic + ' is not a function in searchAgents.py or search.py.')
            print('[SearchAgent] using function %s and heuristic %s' % (fn, heuristic))
            # Note: this bit of Python trickery combines the search algorithm and the heuristic
            self.searchFunction = lambda x: func(x, heuristic=heur)

        # Get the search problem type from the name
        if prob not in globals().keys() or not prob.endswith('Problem'):
            raise AttributeError(prob + ' is not a search problem type in SearchAgents.py.')
        self.searchType = globals()[prob]
        print('[SearchAgent] using problem type ' + prob)

    def registerInitialState(self, state):
        """
        This is the first time that the agent sees the layout of the game
        board. Here, we choose a path to the goal. In this phase, the agent
        should compute the path to the goal and store it in a local variable.
        All of the work is done in this method!

        这是代理第一次看到游戏板的布局。在这里, 我们选择一条通往目标的道路。
        在此阶段, 代理应计算目标的路径并将其存储在局部变量中。
        所有的工作都是用这种方法完成的！

        state: a GameState object (pacman.py)
        状态：游戏状态对象 (pacman.py)
        """
        if self.searchFunction == None: raise Exception("No search function provided for SearchAgent")
        starttime = time.time()
        problem = self.searchType(state) # Makes a new search problem
        self.actions  = self.searchFunction(problem) # Find a path
        if self.actions == None:
            self.actions = []
        totalCost = problem.getCostOfActions(self.actions)
        print('Path found with total cost of %d in %.1f seconds' % (totalCost, time.time() - starttime))
        if '_expanded' in dir(problem): print('Search nodes expanded: %d' % problem._expanded)

    def getAction(self, state):
        """
        Returns the next action in the path chosen earlier (in
        registerInitialState).  Return Directions.STOP if there is no further
        action to take.
        返回前面选择的路径(在 registerInitialState 中)中的下一个操作。 
        返回方向.停止 如果没有进一步的操作要采取。

        state: a GameState object (pacman.py)
        """
        if 'actionIndex' not in dir(self): self.actionIndex = 0
        i = self.actionIndex
        self.actionIndex += 1
        if i < len(self.actions):
            return self.actions[i]
        else:
            return Directions.STOP

class PositionSearchProblem(search.SearchProblem):
    """
    A search problem defines the state space, start state, goal test, successor
    function and cost function.  This search problem can be used to find paths
    to a particular point on the pacman board.
    搜索问题定义了状态空间、开始状态、目标测试、后继函数和成本函数。 
    此搜索问题可用于查找指向吃豆人板上特定点的路径。

    The state space consists of (x,y) positions in a pacman game.
    状态空间由吃豆人游戏中的 (x, y) 位置组成。

    Note: this search problem is fully specified; you should NOT change it.
    注意：此搜索问题已完全指定;你不应该改变它。
    """

    def __init__(self, gameState, costFn = lambda x: 1, goal=(1,1), start=None, warn=True, visualize=True):
        """
        Stores the start and goal.
        存储开始和目标

        gameState: A GameState object (pacman.py)
        costFn: A function from a search state (tuple) to a non-negative number
        goal: A position in the gameState
        """
        self.walls = gameState.getWalls()
        self.startState = gameState.getPacmanPosition()
        if start != None: self.startState = start
        self.goal = goal
        self.costFn = costFn
        self.visualize = visualize
        if warn and (gameState.getNumFood() != 1 or not gameState.hasFood(*goal)):
            print('Warning: this does not look like a regular search maze')

        # For display purposes
        self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE

    def getStartState(self):
        return self.startState

    def isGoalState(self, state):
        isGoal = state == self.goal

        # For display purposes only
        if isGoal and self.visualize:
            self._visitedlist.append(state)
            import __main__
            if '_display' in dir(__main__):
                if 'drawExpandedCells' in dir(__main__._display): #@UndefinedVariable
                    __main__._display.drawExpandedCells(self._visitedlist) #@UndefinedVariable

        return isGoal

    def getSuccessors(self, state):
        """
        Returns successor states, the actions they require, and a cost of 1.
        返回后续状态、它们所需的操作以及开销 1。
        
         As noted in search.py:
             For a given state, this should return a list of triples,
         (successor, action, stepCost), where 'successor' is a
         successor to the current state, 'action' is the action
         required to get there, and 'stepCost' is the incremental
         cost of expanding to that successor
        如 search.py 所述：
            对于给定状态, 这应该返回一个三元组列表(后继者、操作、stepCost), 
            其中“后继者”是当前状态的后继者, “操作”是到达该状态所需的操作, 
            “stepCost”是扩展到该后继状态的增量成本.
        """

        successors = []
        for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
            x,y = state
            dx, dy = Actions.directionToVector(action)
            nextx, nexty = int(x + dx), int(y + dy)
            if not self.walls[nextx][nexty]:
                nextState = (nextx, nexty)
                cost = self.costFn(nextState)
                successors.append( ( nextState, action, cost) )

        # Bookkeeping for display purposes
        self._expanded += 1 # DO NOT CHANGE
        if state not in self._visited:
            self._visited[state] = True
            self._visitedlist.append(state)

        return successors

    def getCostOfActions(self, actions):
        """
        Returns the cost of a particular sequence of actions. If those actions
        include an illegal move, return 999999.
        返回特定操作序列的成本。如果这些操作包含非法移动,请返回999999。
        """
        if actions == None: return 999999
        x,y= self.getStartState()
        cost = 0
        for action in actions:
            # Check figure out the next state and see whether its' legal
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]: return 999999
            cost += self.costFn((x,y))
        return cost

class StayEastSearchAgent(SearchAgent):
    """
    An agent for position search with a cost function that penalizes being in
    positions on the West side of the board.
    具有成本函数的仓位搜索代理, 该函数惩罚处于棋盘西侧的位置。


    The cost function for stepping into a position (x,y) is 1/2^x.
    步入仓位 (x,y) 的成本函数为 1/2^x。
    """
    def __init__(self):
        self.searchFunction = search.uniformCostSearch
        costFn = lambda pos: .5 ** pos[0]
        self.searchType = lambda state: PositionSearchProblem(state, costFn, (1, 1), None, False)

class StayWestSearchAgent(SearchAgent):
    """
    An agent for position search with a cost function that penalizes being in
    positions on the East side of the board.
    具有成本函数的仓位搜索代理, 该函数惩罚处于棋盘东侧的位置。

    The cost function for stepping into a position (x,y) is 2^x.
    步入仓位 (x,y) 的成本函数为 1/2^x。
    """
    def __init__(self):
        self.searchFunction = search.uniformCostSearch
        costFn = lambda pos: 2 ** pos[0]
        self.searchType = lambda state: PositionSearchProblem(state, costFn)

def manhattanHeuristic(position, problem, info={}):
    "The Manhattan distance heuristic for a PositionSearchProblem"
    "位置搜索问题的曼哈顿距离启发式:  |X1-X2|+|Y1-Y2|"
    xy1 = position
    xy2 = problem.goal
    return abs(xy1[0] - xy2[0]) + abs(xy1[1] - xy2[1])

def euclideanHeuristic(position, problem, info={}):
    "The Euclidean distance heuristic for a PositionSearchProblem"
    "位置搜索问题的欧几里得距离启发式:  根号(x1-x2)^2 + (y1-y2)^2"
    xy1 = position
    xy2 = problem.goal
    return ( (xy1[0] - xy2[0]) ** 2 + (xy1[1] - xy2[1]) ** 2 ) ** 0.5

#####################################################
# This portion is incomplete.  Time to write code!  #
#####################################################

class CornersProblem(search.SearchProblem):
    """
    This search problem finds paths through all four corners of a layout.
    此搜索问题查找穿过布局所有四个角的路径。
    You must select a suitable state space and successor function
    您必须选择合适的状态空间和后续函数
    """

    def __init__(self, startingGameState: pacman.GameState):
        """
        Stores the walls, pacman's starting position and corners.
        存储墙壁、吃豆人的起始位置和角落。
        """
        self.walls = startingGameState.getWalls()
        self.startingPosition = startingGameState.getPacmanPosition()
        top, right = self.walls.height-2, self.walls.width-2
        self.corners = ((1,1), (1,top), (right, 1), (right, top))
        for corner in self.corners:
            if not startingGameState.hasFood(*corner):
                print('Warning: no food in corner ' + str(corner))
        self._expanded = 0 # DO NOT CHANGE; Number of search nodes expanded
        # Please add any code here which you would like to use
        # in initializing the problem
        "*** YOUR CODE HERE ***"
        # self.top = top
        # self.right = right

    def getStartState(self):
        """
        Returns the start state (in your state space, not the full Pacman state space)
        返回开始状态(在您的状态空间中, 而不是完整的 Pacman 状态空间中)
        """
        "*** YOUR CODE HERE ***"

        return (self.startingPosition, self.corners)
    
        # util.raiseNotDefined()

    def isGoalState(self, state: Any):
        """
        Returns whether this search state is a goal state of the problem.
        返回此搜索状态是否为问题的目标状态。
        """
        "*** YOUR CODE HERE ***"

        pacmanPos, unvisitedCorners = state
        return unvisitedCorners == (pacmanPos,)
        # util.raiseNotDefined()

    def getSuccessors(self, state: Any):
        """
        Returns successor states, the actions they require, and a cost of 1.
        返回后续状态、它们所需的操作以及开销 1。

         As noted in search.py:
            For a given state, this should return a list of triples, (successor,
            action, stepCost), where 'successor' is a successor to the current
            state, 'action' is the action required to get there, and 'stepCost'
            is the incremental cost of expanding to that successor
        如 search.py 所述：
            对于给定状态, 这应该返回一个三元组列表(后继者、操作、stepCost), 
            其中“后继者”是当前状态的后继者, “操作”是到达该状态所需的操作, 
            “stepCost”是扩展到该后继状态的增量成本
        """
        pacmanPos, unvisitedCorners = state
        successors = []
        for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
            # Add a successor state to the successor list if the action is legal
            # Here's a code snippet for figuring out whether a new position hits a wall:
            #   x,y = currentPosition
            #   dx, dy = Actions.directionToVector(action)
            #   nextx, nexty = int(x + dx), int(y + dy)
            #   hitsWall = self.walls[nextx][nexty]

            "*** YOUR CODE HERE ***"

            x, y = state[0]
            dx, dy = Actions.directionToVector(action)
            nextx, nexty = int(x + dx), int(y + dy)
            hitsWall = self.walls[nextx][nexty]
            
            if hitsWall:
                continue
            
            nextPacmanPos = (nextx, nexty)
            nextUnvisitedCorners = tuple(
                corner for corner in unvisitedCorners if corner != pacmanPos
            )
            nextState = (nextPacmanPos, nextUnvisitedCorners)
            successors.append((nextState, action, 1))


        self._expanded += 1 # DO NOT CHANGE
        return successors

    def getCostOfActions(self, actions):
        """
        Returns the cost of a particular sequence of actions.  If those actions
        include an illegal move, return 999999.  This is implemented for you.
        返回特定操作序列的成本。 如果这些操作包含非法移动, 请返回999999。 这是为您实现的。
        """
        if actions == None: return 999999
        x,y= self.startingPosition
        for action in actions:
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]: return 999999
        return len(actions)


def cornersHeuristic(state, problem):
    """
    A heuristic for the CornersProblem that you defined.
    您定义的角问题启发式方法。

      state:   The current search state
               (a data structure you chose in your search problem)
      状态：当前搜索状态
               (您在搜索问题中选择的数据结构)

      problem: The CornersProblem instance for this layout.
      问题：此布局的 CornersProblem 实例。

    This function should always return a number that is a lower bound on the
    shortest path from the state to a goal of the problem; i.e.  it should be
    admissible (as well as consistent).
    此函数应始终返回一个数字, 该数字是从状态到问题目标的最短路径;即 它应该是可接受(以及一致)。
    """
    corners = problem.corners # These are the corner coordinates
    walls = problem.walls # These are the walls of the maze, as a Grid (game.py)

    "*** YOUR CODE HERE ***"
    def distanceArgmin(pos, points):
        index, minDist = None, 1e9
        for curIdx, curPoint in enumerate(points):
            curDist = util.manhattanDistance(pos, curPoint)
            # curDist = mazeDistance(pos, curPoint, problem.startingGameState)
            if curDist < minDist:
                index, minDist = curIdx, curDist
        return index, minDist

    def optimalPathWithoutWalls(fromPos, throughPoints):
        points = list(throughPoints)
        # print(points)
        pos, pathLength = fromPos, 0
        while points != []:
            index, dist = distanceArgmin(pos, points)
            pathLength += dist
            pos = points[index]
            points.pop(index)
        return pathLength
    return optimalPathWithoutWalls(*state)


class AStarCornersAgent(SearchAgent):
    "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic"
    "食物搜索的搜索代理使用A*和你的食物启发式问题"
    def __init__(self):
        self.searchFunction = lambda prob: search.aStarSearch(prob, cornersHeuristic)
        self.searchType = CornersProblem

class FoodSearchProblem:
    """
    A search problem associated with finding the a path that collects all of the
    food (dots) in a Pacman game.
    与查找在吃豆人游戏中收集所有食物(点)的路径相关的搜索问题。

    A search state in this problem is a tuple ( pacmanPosition, foodGrid ) where
      pacmanPosition: a tuple (x,y) of integers specifying Pacman's position
      foodGrid:       a Grid (see game.py) of either True or False, specifying remaining food

    这个问题中的搜索状态是一个元组(pacmanPosition, foodGrid), 其中
    pacmanPosition: 指定吃豆人位置的整数元组(x, y) 
    foodGrid: 一个True或False的网格(见 game.py), 指定剩余的食物
    """
    def __init__(self, startingGameState: pacman.GameState):
        self.start = (startingGameState.getPacmanPosition(), startingGameState.getFood())
        self.walls = startingGameState.getWalls()
        self.startingGameState = startingGameState
        self._expanded = 0 # DO NOT CHANGE
        self.heuristicInfo = {} # A dictionary for the heuristic to store information

    def getStartState(self):
        return self.start

    def isGoalState(self, state):
        return state[1].count() == 0

    def getSuccessors(self, state):
        "Returns successor states, the actions they require, and a cost of 1."
        "返回后续状态、它们所需的操作以及成本 1"
        successors = []
        self._expanded += 1 # DO NOT CHANGE
        for direction in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
            x,y = state[0]
            dx, dy = Actions.directionToVector(direction)
            nextx, nexty = int(x + dx), int(y + dy)
            if not self.walls[nextx][nexty]:
                nextFood = state[1].copy()
                nextFood[nextx][nexty] = False
                successors.append( ( ((nextx, nexty), nextFood), direction, 1) )
        return successors

    def getCostOfActions(self, actions):
        """Returns the cost of a particular sequence of actions.  If those actions
        include an illegal move, return 999999
        返回特定操作序列的成本。 如果这些行为包括非法移动, 请返回999999
        """
        x,y= self.getStartState()[0]
        cost = 0
        for action in actions:
            # figure out the next state and see whether it's legal
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]:
                return 999999
            cost += 1
        return cost

class AStarFoodSearchAgent(SearchAgent):
    "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic"
    def __init__(self):
        self.searchFunction = lambda prob: search.aStarSearch(prob, foodHeuristic)
        self.searchType = FoodSearchProblem

def foodHeuristic(state: Tuple[Tuple, List[List]], problem: FoodSearchProblem):
    """
    Your heuristic for the FoodSearchProblem goes here.
    你对FoodSearchProblem的启发式方法在这里。

    This heuristic must be consistent to ensure correctness.  First, try to come
    up with an admissible heuristic; almost all admissible heuristics will be
    consistent as well.
    这种启发式方法必须保持一致,以确保正确性。 
    首先,尝试提出一个可接受的启发式方法; 几乎所有可接受的启发式方法都将是一致。

    If using A* ever finds a solution that is worse uniform cost search finds,
    your heuristic is *not* consistent, and probably not admissible!  On the
    other hand, inadmissible or inconsistent heuristics may find optimal
    solutions, so be careful.
    如果使用 A* 找到的统一成本搜索找到的解决方案更差,那么您的启发式方法 *不* 一致,并且可能不被接受！ 
    另一方面,不允许或不一致的启发式方法可能会找到最佳解决方案,因此要小心。

    The state is a tuple ( pacmanPosition, foodGrid ) where foodGrid is a Grid
    (see game.py) of either True or False. You can call foodGrid.asList() to get
    a list of food coordinates instead.
    状态是一个元组(pacmanPosition,foodGrid),其中foodGrid是True或False的Grid(见 game.py)。
    你可以调用foodGrid.asList()来获取食物坐标列表。

    If you want access to info like walls, capsules, etc., you can query the
    problem.  For example, problem.walls gives you a Grid of where the walls
    are.
    如果您想访问墙壁、胶囊等信息,您可以查询问题。 例如,problem.walls为您提供了墙壁所在位置的网格。

    If you want to *store* information to be reused in other calls to the
    heuristic, there is a dictionary called problem.heuristicInfo that you can
    use. For example, if you only want to count the walls once and store that
    value, try: problem.heuristicInfo['wallCount'] = problem.walls.count()
    Subsequent calls to this heuristic can access
    problem.heuristicInfo['wallCount']
    如果你想*存储*信息, 以便在对启发式的其他调用中重用, 可以使用一个名为problem.heuristicInfo的字典。
    例如, 如果您只想对墙壁进行一次计数并存储该值, 
    请尝试: problem.heuristicInfo['wallCount'] = problem.walls.count() 对此启发式的后续调用可以访问
    problem.heuristicInfo['wallCount']
    """
    position, foodGrid = state                  # 获取位置和食物
    "*** YOUR CODE HERE ***"

    '''-------------------------------------------------------------------------------'''
    result = 0                                  # 初始化结果变量为 0
    foods = []                                  # 存储所有剩余食物的坐标
    food_pair = ((0,0),(0,0),0)                 # 存储最远的食物对的坐标和曼哈顿距离

    for i in range(0,foodGrid.width):           # 遍历foodGrid，得到当前食物的坐标
        for j in range(0,foodGrid.height):
            if (foodGrid[i][j] == True):        # 如果单元格中有食物
                foods.append((i,j))             # 将食物坐标添加到 foods 列表中

    if (len(foods) == 0):                       # 如果地图上没有食物了,返回 0
        return 0
    for current_food in foods:                  # 找到最远的一对食物
        for select_food in foods:     
            if(current_food==select_food):      # 如果两个食物坐标相同，跳过
                continue
            else:
                distance = util.manhattanDistance(current_food,select_food) #计算两个食物的曼哈顿距离
                if(food_pair[2] < distance):    # 如果当前距离大于已知距离，则更新最远距离
                    food_pair = (current_food,select_food,distance)

    if(food_pair[0]==(0,0) and food_pair[1]==(0,0)):  # 如果最远的食物对没有找到，则使用 Pacman 到第一个食物的曼哈顿距离作为启发式值             
        result = util.manhattanDistance(position,foods[0])
    else: 
        d1 = util.manhattanDistance(position,food_pair[0])
        d2 = util.manhattanDistance(position,food_pair[1])
        result = food_pair[2] + min(d1,d2)              # 根据最远的一对食物和 Pacman 的位置计算启发式值

    return result

    # return 0

class ClosestDotSearchAgent(SearchAgent):
    "Search for all food using a sequence of searches"
    "使用一系列搜索搜索所有食物"
    def registerInitialState(self, state):
        self.actions = []
        currentState = state
        while(currentState.getFood().count() > 0):
            nextPathSegment = self.findPathToClosestDot(currentState) # The missing piece
            self.actions += nextPathSegment
            for action in nextPathSegment:
                legal = currentState.getLegalActions()
                if action not in legal:
                    t = (str(action), str(currentState))
                    raise Exception('findPathToClosestDot returned an illegal move: %s!\n%s' % t)
                currentState = currentState.generateSuccessor(0, action)
        self.actionIndex = 0
        print('Path found with cost %d.' % len(self.actions))

    def findPathToClosestDot(self, gameState: pacman.GameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from gameState.
        返回从 gameState 开始的到最接近点的路径（操作列表）。
        """
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"

        return search.breadthFirstSearch(problem)       # 宽度优先，保证找到的是最近的食物
    
        # util.raiseNotDefined()

class AnyFoodSearchProblem(PositionSearchProblem):
    """
    A search problem for finding a path to any food.
    寻找任何食物路径的搜索问题。

    This search problem is just like the PositionSearchProblem, but has a
    different goal test, which you need to fill in below.  The state space and
    successor function do not need to be changed.
    这个搜索问题就像PositionSearchProblem一样, 但有一个不同的目标测试, 你需要在下面填写。 
    不需要更改状态空间和后续函数。

    The class definition above, AnyFoodSearchProblem(PositionSearchProblem),
    inherits the methods of the PositionSearchProblem.
    上面的类定义 AnyFoodSearchProblem(PositionSearchProblem) 继承了 PositionSearchProblem 的方法。

    You can use this search problem to help you fill in the findPathToClosestDot method.
    您可以使用此搜索问题来帮助您填写 findPathToClosestDot 方法。
    """

    def __init__(self, gameState):
        "Stores information from the gameState.  You don't need to change this."
        "存储来自游戏状态的信息。 您无需更改此设置"
        # Store the food for later reference
        self.food = gameState.getFood()

        # Store info for the PositionSearchProblem (no need to change this)
        self.walls = gameState.getWalls()
        self.startState = gameState.getPacmanPosition()
        self.costFn = lambda x: 1
        self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE

    def isGoalState(self, state: Tuple[int, int]):
        """
        The state is Pacman's position. Fill this in with a goal test that will
        complete the problem definition.
        状态是吃豆人的立场。用目标测试填写, 以完成问题定义。
        """
        x,y = state                     #将元组解压缩为两个独立的变量“x”和“y”

        "*** YOUR CODE HERE ***"

        if(self.food[x][y] == True):    #如果“x”和“y”指定的位置包含食物，则返回True
            return True
        else:                           #如果指定位置没有食物，则返回False
            return False

        # util.raiseNotDefined()

def mazeDistance(point1: Tuple[int, int], point2: Tuple[int, int], gameState: pacman.GameState) -> int:
    """
    Returns the maze distance between any two points, using the search functions
    you have already built. The gameState can be any game state -- Pacman's
    position in that state is ignored.
    使用已构建的搜索函数返回任意两点之间的迷宫距离。
    gameState 可以是任何游戏状态——吃豆人在该状态下的位置将被忽略。

    Example usage: mazeDistance( (2,4), (5,6), gameState)
    示例用法：迷宫距离( (2, 4),  (5, 6),  游戏状态)

    This might be a useful helper function for your ApproximateSearchAgent.
    对于您的ApproximateSearchAgent来说, 这可能是一个有用的帮助程序函数。
    """
    x1, y1 = point1
    x2, y2 = point2
    walls = gameState.getWalls()
    assert not walls[x1][y1], 'point1 is a wall: ' + str(point1)
    assert not walls[x2][y2], 'point2 is a wall: ' + str(point2)
    prob = PositionSearchProblem(gameState, start=point1, goal=point2, warn=False, visualize=False)
    return len(search.bfs(prob))
